package C055;

import java.util.Arrays;

/**
 * ClassName: C01
 * Package: C055
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/10 14:22
 * @Version 1.0
 * @Since 1.0
 */
public class C01 {
    public static void main(String[] args) {
        int[] arr = {2,-1,2};
        System.out.println(shortestSubarray(arr, 3));
    }

    static int MAXLEN = 100001;
    static long[] sum = new long[MAXLEN];
    static int[] deque = new int[MAXLEN];
    static int h, t, n;
    public static int shortestSubarray(int[] nums, int k) {
        n = nums.length;
        h = t = 0;
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            while(h < t && sum[i] - sum[deque[h]] >= k) {
                ans = Math.min(ans, i - deque[h++]);
            }
            while(h < t && sum[i] <= sum[deque[t - 1]]) {
                t--;
            }
            deque[t++] = i;
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }


}
